// 每日一题系列：
// fibonacci数列（面试常考）

// 递归
function Fibonacci(n){
    if(n <= 0) return 0;
    if(n === 1) return 1;
    return Fibonacci(n - 1) + Fibonacci(n - 2);
}
// 除了这种解法你还能想到哪些呢？
// 晚上十点之前把答案提交到仓库，十点之后会上传答案

//尾调用优化
function Fibonacci4(n,fibOne = 0,fibTwo = 1){
    if(n === 0)
        return fibOne;
    if(n === 1)
        return fibTwo;
    return Fibonacci4(n - 1,fibTwo,fibOne + fibTwo);
}

// 优化递归 + 数组缓存  注：考过
let FibonacciByArrayCache = function() {
    let temp = [0,1];
    return function (n) {
        if(n < 2) return temp[n];
        let result = temp[n]; //undefined
        if(typeof result != 'number'){
            result = FibonacciByArrayCache(n - 1) + FibonacciByArrayCache(n - 2);
            temp[n] = result;
        }
        return result;
    }
}();
// console.log(FibonacciByArrayCache(3));

// 动态规划：从底部开始解决问题，将所有小问题解决掉，然后合并成一个整体解决方案，从而解决掉整个大问题；
// 递归：从顶部开始将问题分解，通过解决掉所有分解的小问题来解决整个问题；
// 由C++转ES5普通写法
function Fibonacci2(n){
    let result = [0,1];
    if(n < 2){
        return result[n];
    }
    let fibOne = 0;
    let fibTwo = 1;
    let fibN = 0;
    for(let i = 2;i < n ;i ++){
        fibN = fibOne + fibTwo;
        fibOne = fibTwo;
        fibTwo = fibN
    }
    return fibN;
}

function Fibonacci3(n) {
    let fibOne = 0;
    let fibTwo = 1;
    for(let i = 0;i < n;i ++){
        [fibOne,fibTwo] = [fibTwo, fibOne + fibTwo];
    }
    return fibOne;
}

console.log(Fibonacci4(4));